import random
from bag import *

def rows(file, bad=r'["\' \t\r\n]',sep=',') :
  for line in open(file,'r') :
    line = re.sub(bad,"",line).split(sep)
    if line: yield line
        
class Row:
  id = 0
  dists = {}
  def __init__(r,t,data):
    Row.id += 1
    self.id = Row.id
    self.table = t
    self.data = data
  def klassi(r) : return [len(r.data) - 1]
  def discretize(r,breaks) :
    for col in r.table.nums:
      r.data[col] = bin(r.data[col],breaks[col]) 
  def __sub__(r1,r2):
    if r1.id > r2.id: r1,r2 = r2,r1
    key = (r1.id,r2.id)
    if key in Row.dists : return Row.dists[key]
    out = Row.dists[key] = distance(r1,r2,r1.table.headers)
    return out
  
def distance(r1,r2,things):
  n=total=0
  for col,thing in enumerate(things):
    if thing.isKlass : continue
    n  += 1
    a   = r1.data[col]
    b   = r2.data[col]
    tmp = 1
    if a == b:
      if a != '?' : tmp=0
    else:
      if thing.isNumeric():
        lo = thing.min
        hi = thing.max
        if lo == hi: tmp = 0
        else:
          half = (hi - lo)/2.0 
          if a == '?' : a = (lo if b > half else hi)
          if b == '?' : b = (lo if a > half else hi)
          a   = (a - lo) / (hi - lo)
          b   = (b - lo) / (hi - lo)
          tmp = a - b
    total += thing.weight*(tmp**2)
  return total**0.5/n**0.5  


class Table:      
  def ready(t,lst,prep=lambda x: x) :
    t.data=[]; t.nums=[]; t.syms=[]
    t.header=lst
    for i,name in enumerate(lst):
      isKlass = i == (len(lst) - 1)
      if "$" in name: 
        t.nums.append(Num(i,prep,isKlass))
      else:
        t.syms.append(Sym(i,isKlass))
  def put(t,lst) :
    tmp = [t.header[i].put(x) for i,x in enumerate(lst)]
    t.data.append(Row(tmp))
  def slurp(t,file) :
    for lst in rows(file):
      if not t.header: t.ready(lst,prep=float)
      else           : t.put(lst)
  def disretize(t,bins=5) :
    tmp = zip(*self.data)
    for i in t.nums : 
      b = t.header[i].getBreaks(tmp[i],bins)
      tmp[i] = [bin(num,t,b) for x in tmp[i]]
    self.data = zip(*tmp)
  def closest(t,r1, best = 10**32,
                    better=lambda x,y: x < y):
    for r2 in self.data:
      if r1.id != r2.id:
        tmp = r1 - r2
        if better(tmp,out): best,out=tmp,r2
    return out
  def furthest(t,r1)  : 
    return t.closest(r1,-1,lambda x,y: x > y)

class FastMap:
  def __init__(f,t): f.table=t
  def furthest2(f) :
    any  = random.randint(0,len(f.table.data))
    west = f.table.furthest(any)
    east = t.table.furthest(west)
    return west,east, west - east
  def project(f,row,west,east,c) :
    a = row - west
    b = row - east
    if a >= c: return c
    if b >= c: return 0
    return  (a**2 + c**2 - b**2) / (2*c)
  def projections(f) :
    west,east,c = f.furthest2()
    return [f.project(row,west,east,c),row for row in f.table.data]
  def split(f): 
    def x(this) : return this[0]
    def row(this) : return this[1]
    p = f.projections()
    p = sorted(p,key=x)
    i = int(len(p)/2)
    while i < len(p)-1 and x(p[i]) == x(p[i+1]) : i += 1
    return map(row,out[:i]),map(row,out[i:])

def breaks(nums0,bins=5) :
   def chunks():
    start  = stop = 0 
    while stop  < n: 
      start = stop  
      stop = start + d 
      while stop < n-1 and nums[stop-1] == nums[stop]: 
        stop += 1
      if stop + d >= n : 
        stop = n 
      yield nums[start:stop]
   nums = sorted([x for x in nums0 if x != "?"])
   n    = len(nums)
   d    = max(1,int(n/bins))
   tmp  = [Bag(lst=chunk) for chunk in chunks()]
   return rc(tmp, minObs = d)

def bin(val,breaks, ninf = -10*10) :
  if val == "?": return val
    before, last = ninf, 0
    for i,now in enumerate(breaks) :
      if val > before and val <= now: return i
        before, last  = now, i
  return last+1

class Thing:
  def put(self,x) : 
    return x if x == '?' else self.put1(x)
  
class Num(Thing):
    def isNumeric(n)    : return True
    def __init__(n,i,prep,isKlass) : 
      n.breaks=[]
      n.weight=1; n.isKlass = isKlass; n.prep= prep; 
      n.i = i; n.max= -10**32 ; n.min = -1*n.max
    def put1(n,x)     : 
      x = n.prep(x); n.max= max(n.max,x); 
      n.min= min(n.min,x); return x
    def getBreaks(n,nums,bin) :
      n.breaks = breaks(nums,bins)
      return n.breaks

class Sym(Thing):
    def isNumeric(x)  : return False
    def __init__(s,i,isKlass) : 
      s.weight=1; s.isKlass=isKlass; s.i = i; s.counts={}; s.most = -1
    def put1(n,x)     : 
      new = s.counts[x] = s.counts.get(x,0) + 1
      if new > most : most,mode=new,x
      return x

def often(seq,max=100,
          item   = lambda x: x,
          weight = lambda x: x.priority) :
    total = 0
    for x in seq: total += weight(x)
    while True:
        max -= 1
        if max < 0 : break
        chosen = random.uniform(0, total)
        count  = 0
        for x in seq:
            count += weight(x)
            if count > chosen:
                yield item(x)
                break
            
def first(x)  : return x[0]
def second(x) : return x[1]

#for x in often([[1,10],[2,20],[8,30]],max=20,item=second,weight=first):
 #   print x
